package com.lucifer;

/**
 * 自己写几个排序算法的代码
 *
 * @author yuxiao05@meituan.com
 * @create 2016-07-06 上午10:38
 */

public class SortCase {

  private static final int INSERTION_THREAD = 3;

  public static void main(String[] args){
    int[] a = new int[]{2,1,4,5,3,2,6};

    //countingSort(a, 0, a.length - 1);
    //insertionSort(a, 0, a.length - 1);
    mergeSort(a, 0, a.length - 1);

    for (int i : a) {
      System.out.println(i);
    }
  }

  /**
   * 计数排序,牢记
   * @param arr
   * @param left
   * @param right
   */
  public static void countingSort(int arr[], int left, int right) {
    int[] count  = new int[10];

    for (int i = left - 1; ++i <= right; count[arr[i]]++);

    for (int i = count.length, k = right; k >= left;) {
      while (count[--i] == 0);

      int value = i;
      int s = count[i];

      do {
        arr[k--] = value;
      }while (--s > 0);
    }
  }

  /**
   * 插入排序,牢记
   * @param arr
   * @param left
   * @param right
   */
  public static void insertionSort(int arr[], int left, int right) {

    for (int i = left, j = i; i < right ; j = ++i) {
      int ai = arr[i + 1];
      while (ai < arr[j]) {
        arr[j + 1] = arr[j];
        if (j-- == 0)
          break;
      }
      arr[j + 1] = ai;
    }
  }

  /**
   * 归并排序
   * @param arr
   * @param left
   * @param right
   */
  public static void mergeSort(int arr[], int left, int right) {
    int length = right - left + 1;
    if (length < INSERTION_THREAD) {
      insertionSort(arr, left, right);
      return;
    }

    int mid = (left + right) >>> 1;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid, right);

    if (arr[mid - 1] < arr[mid]) {
      System.arraycopy(arr, left, arr, left, length);
      return;
    }
    int[] tmp = new int[length];
    for (int i = 0, p = left, q = mid; i < length; i++) {
      if (p < q && arr[p] < arr[q])
        tmp[i] = arr[p++];
      else
        tmp[i] = arr[q++];
    }
  }

  /**
   * 快速排序
   * @param arr
   * @param left
   * @param right
   */
  public void quickSort(int arr[], int left, int right) {

  }
}
